package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;
import cn.pugle.oj.catalog.Unknown;

/**
 * 更秀的是这个直接四行递归
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/65225/4-lines-C%2B%2BJavaPythonRuby
 * 是一个前序遍历
 * 利用了 树元素unique 和 必定有答案(pq必定在树中, line21) 的特性
 *
 * @author tzp
 * @since 2020/12/19
 */
public class LC236_1 implements TreeProblem {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left == null ? right : right == null ? left : root;
    }

    public static void main(String[] args) {
        System.out.println(new LC236_1());
    }
}
